A complex object is an instance of a data type or objected-oriented class that contains zero or more scalar attributes (e.g. integers, characters, etc.) and one or more attributes that can point to or reference other complex objects. An attribute capable of pointing to or referencing another object is referred to herein as a "pointer." Thus, a complex object may be mapped to a top-level data structure with one or more pointers to other data structures that in turn may have pointers to other data structures. Examples of complex objects include linked lists, trees, and graphs.
Memory to store complex objects is typically dynamically allocated from an area of memory available to a program called a "heap." More specifically, each data structure in the complex object, including the complex objects to which the complex object has pointers, is individually allocated from the heap and referenced by a pointer. Thus, a top-level data structure of a complex object includes pointers to secondarily allocated data structures. When a complex object is no longer needed by the program, the individually allocated data structures of the complex object are deallocated or "freed" to allow the memory currently being used to store the complex object to be recycled (i.e. to be made available for other purposes). Thus, freeing a complex object involves freeing each allocated data structure belonging to the complex object.
A routine is a self-consistent set of computer instructions for performing particular tasks. Routines are also known as procedures, functions, and subroutines. The computer instructions can be low-level machine language instructions or high-level instructions in a programming language such as a C or C++ that are ultimately translated into machine language instructions, for example, by compiling or interpreting. Calling or invoking a routine involves passing arguments to the routines, if necessary, and causing the instructions to be executed. A routine may also return one or more results to the calling routine, and these results can be complex objects. Non-complex objects have a predetermined size, and space to hold the returned results of non-complex objects is reserved on the stack frame or register set for the calling routine. Memory management for stack-based objects is straightforward because the entire stack frame for a routine is automatically deallocated when execution of the routine is finished (i.e. when the routine "returns"). Thus, simple, stack-based objects do not need to be deallocated explicitly.
Complex objects, on the other hand, usually do not have a predetermined size; thus, complex objects that are returned from a routine are dynamically allocated from heap memory. The dynamic memory allocation may be performed by a vendor-supplied operating system or run-time library call, such as malloc(3) on Unix operating system platforms, or by a user-supplied memory allocation routine that ultimately makes an independent call to a vendor-supplied memory allocation routine. This type of memory allocation typically results in the dispersion of a complex object over many non-contiguous areas of the heap, because, after many allocations and deallocation, the heap is fragmented. For example, in FIG. 6, a call to routine "f" in step 600 causes a complex object "p" to be returned. Complex object "p" comprises five non-contiguous areas of memory in heap 610, each labeled "p." In addition, a subsequent call to routine "g" in step 602 causes complex object "q" to be returned, consuming four non-contiguous areas of memory in the heap. Heap 612 illustrates the heap 610 after memory has been allocated for complex object "q".
Unlike the memory occupied by the stack frame, which is automatically deallocated upon a routine's return, heap-allocated memory for a complex object must be explicitly deallocated when the complex object is no longer needed by the program. This deallocation typically involves traversing the structure of the complex object by following pointers stored in the various data structures that make up the complex object. These pointers are followed to locate and deallocate the various non-contiguous areas of the heap used to store the data structures belonging to the complex parameter.
Since traversing a complex data structure is type-dependent, a deallocation routine is written for each complex object. Referring again FIG. 6, the complex object "p" is deallocated by calling a type-specific deallocation routine called "P_free( )" with the complex object "p" passed in as a parameter. In response, the complex object "p" is traversed and each of the dynamically alloacted memory areas that belong to "p" are freed (step 604). Heap 614 illustrates the state of heap 612 after memory for "p" is no longer allocated. Likewise, complex object "q" is deallocated by calling a different "Q_free( )" routine in step 606. The "Q_free( )" routine traverses the data structures of complex object "q" and frees the individually allocated memory areas of the complex object. Heap 616 illustrates heap 614 after complex object "q" has been deallocated. Therefore, this "per-object" deallocation approach can be computationally expensive, and the computational cost for performing deallocation for a complex object increases with the complexity of the object.
A "per-client" memory management approach that may reduce the computational expense in deallocating complex objects is available in the Distributed Computing Environment (DCE) defined by the Open Software Foundation (OSF). According to this approach, the following function call is made before calling client stub routines that return complex objects: rpc_ss_set_client_alloc_free(rpc_ss_allocate, rpc_ss_free);
When called, this routine instantiates a new dynamic memory management system for the process and registers new memory allocation and deallocation routines. When the called client stub routines return complex objects, the client stub routines invoke the registered memory allocation routine, rpc_ss_allocate, to dynamically allocate memory for the complex objects within the new memory management system. When all of the complex objects are no longer needed outside the client stub routines that created them, the entire new memory management system may be torn down, releasing all the memory allocated for the complex objects. This process may be performed by a rpc_ss_disable_allocate( ) function call.
Referring the FIG. 7, a new memory management system is instantiated by calling the enable routine in step 700, which registers an appropriate memory allocation routine for the new memory management system and sets up an area 720 in heap 710 for allocating memory. In step 702, when complex object "p" is returned from function "f", memory for complex object "p" is allocated by the registered memory allocation routine from memory area 720 as shown in heap 712. When function "g" is called in step 704, memory for complex object "q" is also allocated from memory area 720 as shown in heap 714. Finally, after both complex object "p" and complex object "q" are no longer needed, the new memory management system can be disabled in step 706, releasing the memory for all the allocated memory, including complex objects "p" and "q". Heap 716 depicts heap 714 after the disable call routine is executed.
Although the process of tearing down the memory management system to release the memory for all the allocated complex objects can be less computationally expensive than the "per-object" deallocation approach, the "per-client" approach is less flexible, because different complex objects typically have different and overlapping lifetimes. The lifetime of a complex object is the period from the creation of the complex object until the last use of the complex object. For example, referring back to FIG. 7, the lifetime 732 of complex object "q" commences at step 704 and ends when it is no longer needs at step 706, where it can be safely deallocated. In this example, the lifetime 730 of complex object "p" commences at step 702, extends beyond the creation of complex object "q" in step 704, and ends some time before the end of the lifetime 732 of complex object "q". Consequently, the lifetime 730 of complex object "p" overlaps the lifetime 732 of complex object "q" because complex object "q" was created after complex object "p" was created but before complex object "p" was terminated.
In this situation, the "per-client" memory management system cannot be taken down at the end of the lifetime 730 of complex object "p" because deallocation of memory area 720 will prematurely release the allocated memory for complex object "q". In contrast, the "per-object" deallocation allows the complex object to be freed at the end of its lifetime. Referring again to FIG. 6, complex object "p" is freed in step 604 at the end of its lifetime 620, and complex object "q" is freed in step 606 at the end of its lifetime 622.
One conventional attempt to handle overlapping lifetimes is convert a complex object from a "per-client" memory management approach to a "per-object" memory management approach. Accordingly, the complex object is cloned from the "per-client" memory management area into a more persistent area of the heap by performing a deep copy operation on the complex object. A deep copy, however, is a computationally expensive operation because the complex object data structure needs to be traversed to visit every node in the complex object for copying. Furthermore, freeing the cloned complex object requires the expensive traversal of the complex object as in the "per-object" approach. Consequently, the conscientious programmer is faced with a dilemma: either defer the deallocation of the memory for complex object "p", thereby wasting memory resources, or deallocate complex object "p" according to the "per-object" approach and incur the computational overhead of traversing the data structures and pointers of complex object "p".
Another problem with the "per-client" approach is that it is error-prone. There are several operations an application programmer must code for every procedure call that returns complex objects, and it is easy to overlook or miscode one of the operations, resulting in a bug that causes the program to malfunction. For example, the application programmer may instantiate a new memory management system without realizing that another memory management system is in effect, thereby causing the previously allocated memory to be lost. Memory allocation errors are usually very subtle and are some of the most difficult bugs to diagnose and fix.
Therefore, there is a need for a memory management system and methodology that avoids the computational costs in traversing complex objects present in the conventional "per-object" deallocation approach while avoiding the loss of flexibility incurred by using the "per-client" deallocation approach. There is also a need for reducing bugs in implementing a memory management system.